package com.algrithom.tree.twotree;

import java.io.PrintStream;

import org.apache.commons.lang3.math.NumberUtils;

import com.common.model.TreeNode;

/**
 * 二叉搜索树 根节点大于或等于左节点，小于或等于右节点 这里需要区别于大顶堆和小顶堆
 *
 * @author think
 * @version 2019/10/28
 */
public class BinarySearchTree {
    
    public static void main(String[] args){
        int[] arr = {10,5,15,3,7,13,17,2,4,6,8,11,14,16,18};
        PrintStream pw = System.out;
        TreeNode root = createBST(arr);
        preOrder(root);
        pw.println();
        root = delete(root,search(root,10));
        preOrder(root);
    }
    
    /**
     * 删除一个二叉搜索树中任意节点
     *
     * @param root 二叉树根节点
     * @param s 所要删除的节点
     * @return 返回根节点
     */
    private static TreeNode delete(TreeNode root,TreeNode s){
        if (s == null) {
            return root;
        }
        /* 下面采用的是假根节点法，让代码更简洁 */
        TreeNode temp = new TreeNode(-1);
        temp.setRightChild(root);
        root.setParent(temp);
        /* 首先判别若要删除节点左右节点都为空的情况 */
        if (s.getLeftChild() == null && s.getRightChild() == null) {
            if (s == s.getParent().getRightChild()) {
                s.getParent().setRightChild(null);
            } else {
                s.getParent().setLeftChild(null);
            }
        } else if (s.getLeftChild() == null && s.getRightChild() != null) {
            if (s == s.getParent().getRightChild()) {
                s.getParent().setRightChild(s.getRightChild());
            } else {
                s.getParent().setLeftChild(s.getRightChild());
            }
            s.getRightChild().setParent(s.getParent());
        } else if (s.getRightChild() == null && s.getLeftChild() != null) {
            if (s == s.getParent().getRightChild()) {
                s.getParent().setRightChild(s.getLeftChild());
            } else {
                s.getParent().setLeftChild(s.getLeftChild());
            }
            s.getLeftChild().setParent(s.getParent());
        } else {
            // 左右子树都不为空的情况
            TreeNode next = nextNode(s);
            // 先找到要删除节点的后驱节点
            /* 若后驱结点不是要删除节点的右子树根节点，那可以得出后驱节点左子树一定是空，而且一定不在父节点的右子树上 */
            /* 于是先将该节点的父节点和右子树根节点连接，再把该节点右子树替换为要删除节点的右子树，并置替换节点右子树父亲节点为该节点 */
            if (next != s.getRightChild()) {
                next.getParent().setLeftChild(next.getRightChild());
                if (next.getRightChild() != null) {
                    next.getRightChild().setParent(next.getParent());
                }
                next.setRightChild(s.getRightChild());
                s.getRightChild().setParent(next);
            }
            /* 判断要删除节点和父亲节点的左右关系，并替换为后驱节点 */
            if (s == s.getParent().getLeftChild()) {
                s.getParent().setLeftChild(next);
            } else {
                s.getParent().setRightChild(next);
            }
            // 置替换后的节点父亲节点为删除节点父亲节点
            next.setParent(s.getParent());
            /* 处理下与左子树的关系 */
            next.setLeftChild(s.getLeftChild());
            s.getLeftChild().setParent(next);
        }
        /* 将假的头抽走，取出真的root节点 */
        root = temp.getRightChild();
        root.setParent(null);
        return root;
    }
    
    /**
     * 二叉搜索树的查找算法
     *
     * @param root 输入节点
     * @param value 查找的数值
     * @return 返回该节点引用，没有则返回空
     */
    private static <T> TreeNode<T> search(TreeNode<T> root,int value){
        if (root == null || root.getValue().equals(value)) {
            return root;
        }
        if (NumberUtils.compare(Integer.parseInt(String.valueOf(root.getValue())),value) < 0) {
            return search(root.getLeftChild(),value);
        } else {
            return search(root.getRightChild(),value);
        }
    }
    
    /**
     * 二叉搜索树里任意一个节点的下一个邻近的节点（数值上来看）也叫后驱节点
     *
     * @param root 跟节点
     * @return 返回其引用
     */
    private static TreeNode nextNode(TreeNode root){
        if (root.getRightChild() != null) {
            return MinTree(root.getRightChild());
        }
        TreeNode temp = root.getParent();
        while (temp != null && root == temp.getRightChild()) {
            root = temp;
            temp = temp.getParent();
        }
        return temp;
    }
    
    /**
     * 查找搜索树的最小树节点
     *
     * @param root
     * @return
     */
    private static TreeNode MinTree(TreeNode root){
        // TODO Auto-generated method stub
        if (root == null) {
            return null;
        }
        TreeNode temp = root;
        while (temp.getLeftChild() != null) {
            temp = temp.getLeftChild();
        }
        return temp;
    }
    
    /**
     * 返回二叉搜索树的最大树节点
     *
     * @param root 输入根节点
     * @return
     */
    private static TreeNode maxTree(TreeNode root){
        if (root == null) {
            return null;
        }
        TreeNode temp = root;
        while (temp.getRightChild() != null) {
            temp = temp.getRightChild();
        }
        return temp;
    }
    
    /**
     * 前序遍历
     *
     * @param root 输入根节点
     */
    private static void preOrder(TreeNode root){
        if (root == null) {
            return;
        }
        System.out.print(root.getValue() + "-");
        preOrder(root.getLeftChild());
        preOrder(root.getRightChild());
    }
    
    /**
     * 建立一颗二叉搜索树的算法
     *
     * @param arr 输入参数，一个任意数组
     * @return 返回该树根节点
     */
    private static TreeNode createBST(int[] arr){
        // TODO Auto-generated method stub
        TreeNode root = null;
        if (arr == null || arr.length == 0) {
            return root;
        }
        
        root = new TreeNode(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            insertTree(root,arr[i],null);
        }
        return root;
    }
    
    /**
     * 二叉搜索树插入一个数值
     *
     * @param root 待插入二叉搜索树的根节点
     * @param i 待插入数值
     * @param parent 父节点引用
     * @return 返回插入后的节点，递归调用
     */
    private static <T> TreeNode<T> insertTree(TreeNode<T> root,int i,TreeNode parent){
        if (root == null) {
            root = new TreeNode(i);
            root.setParent(parent);
        } else {
            if (NumberUtils.compare(Integer.parseInt(String.valueOf(root.getValue())),i) < 0) {
                root.setLeftChild(insertTree(root.getLeftChild(),i,root));
            } else {
                root.setRightChild(insertTree(root.getRightChild(),i,root));
            }
        }
        return root;
    }
}
